"""
任务1、打印一个6行的杨辉三角

分析：
1.第n行有n+1项，n是正整数。
2.每个数字等于它上方两数之和。
"""
def test01():
    line = int(input('>>>'))
    triangle = []
    for i in range(line):
        # 行首处理
        row = [1]  # 初始化head
        triangle.append(row)  # 将head列表作为元素插入triangle列表中。
        # 行中处理
        if i == 0:
            continue
        for j in range(i - 1):  # 只有i等于2，即第三行时进入，j的范围是2~i-1
            row.append(triangle[i - 1][j] + triangle[i - 1][j + 1])  # 调整head的值，进行计算。
        # 行尾处理
        row.append(1)  # 调整head的值，尾部追加1。
    print(triangle)

def test02():
    line = int(input('>>>'))
    oldline = []
    newline = [1]
    print(newline)  # 打印第一个数。
    for i in range(1, line):  # 当i等于1时进入。
        oldline = newline.copy()  # 复制上一行的列表。
        oldline.append(0)  # 上一行的列表尾部填0补齐，和下一行数量一致。
        newline.clear()  # 此时newline还存放着上一行的值，清空。
        for j in range(i + 1):
            newline.append(oldline[j - 1] + oldline[j])  # 根据oldline上一行计算
        print(newline)  # 将得到的这行打印出来。

"""
这两种方式其实逻辑都是一样，实现的方式不一样。
第一种是只利用列表的索引完成求和；而第二种是利用两个列表完成求和。

代码优化：
1、内存复杂度优化：能不能一次性开辟空间，使用列表解析式和循环迭代。
2、时间复杂度优化：能不能少算一半的数字
"""

# 首先实现空间开辟，两边填1，中间填0
def test03():
    triangle = []
    n = 6
    for i in range(n):  # i用作控制行
        row = [1]  # row列表是每行的容器
        for k in range(i):  # k用作控制列
            row.append(1) if k == i - 1 else row.append(0)
        triangle.append(row)  # triangle是整个杨辉三角的容器
    print(triangle)

def test03_01():
    triangle = []
    n = 6
    for i in range(n):  # i用作控制行,i的范围0~6
        row = [1]  # row列表是每行的容器
        for k in range(i):  # k用作控制列,k的范围0~i
            row.append(1) if k == i - 1 else row.append(0)
        triangle.append(row)  # triangle是整个杨辉三角的容器

        if i == 0:  # i用作控制行,i的范围0~6
            continue

        for j in range(1, i // 2 + 1):  # k用作控制列，k的范围1~i//2+1
            val = triangle[i - 1][j - 1] + triangle[i - 1][j]
            row[j] = val

            if j != i - j:
                row[-j - 1] = val
    print(triangle)

# 测试
# test01()
# test02()
# test03()
test03_01()
